/*
 * GraphSPT.java
 *
 * Created on 13 de febrero de 2007, 09:37 AM
 */

package networkFlow;

/**
 *
 * @author tavobula
 */
public class GraphSPT{
    private int[] wt;
    private int c;
    
    /** Creates a new instance of GraphSPT */
    public GraphSPT(Network G, int s) {
        int V=G.getV(), N=0, iteration=0;
        boolean cycle=false;
        c=-1;
        wt=new int[V];
        for(int v=0; v<V; v++){
            wt[v]=V*145*2;
        }
        intQueue Q = new intQueue(G.getV());
        wt[s]=0;
        Q.put(s);
        Q.put(V);
        iteration=1;
        while(!Q.empty()){
            int v;
            while((v=Q.get())==V){
                if(N++>V) return;
                iteration=iteration+1;
                if(iteration==V) cycle=true;
                Q.put(V);
            }
            AdjList A=G.getAdjList(v);
            for(Edge e=A.beg();!A.end();e=A.nxt()){
                int w=e.other(v);
                int cap=e.capRto(w);
                int cost=e.costRto(v);
                int P=wt[v]+cost;
                if(cap>0&P<wt[w]){
                    wt[w]=P;
                    Q.put(w);
                    if(cycle){c=w; return;}
                }
            }
        }
        
    }
    
    
    
    int cycle(){
        return c;
    }
    
}


